NetLogo User Community Models

(back to the NetLogo User Community Models)

Download If clicking does not initiate a download, try right clicking or control clicking and choosing "Save" or "Download".(The run link is disabled because this model uses extensions.)

WHAT IS IT?

This model demonstrates the first application of an improved clonal selection algorithm to a traveling salesman problem (Eil51). Clonal selection algorithm is one of the most famous biologically-inspired artificial immune system algorithm. Traditional clonal selection algorithm works by generating a random antibody population of solutions for a problem, evaluating those solutions and then using cloning and hypermutation to create new solutions to the problem. But experiments showed that this traditional method has low performance to solve the traveling salesman problems. Thus, in the present model crossover mechanism [1] and receptor-editing process [2] are integrated into traditional clonal selection algorithm.

In the present model "real valued vectors shape space" is used to represent solutions.

"1 / travel tour distance" metric is used as the affinity measure.

HOW IT WORKS

The improved clonal selection algorithm is composed of the following steps.

Step 1: Create an antibody population of random solutions (parameter:
initial-population-size). Each antibody has a solution vector which is created randomly.

Step 2: Calculate affinity for each antibody.

Step 3: According the affinity, select n antibodies and sort in descending order.
(A1, A2, ... , An) (parameter: selection-size)

Step 4: Clone the selected antibodies. (parameter: clone-size)

Step 5: Hypermutate and receptor-editing process. Update affinities.

Step 6: Crossover process. Update affinities.

Step 7: According the affinity of antibodies that are created in step 5 and step 6,
re-select n antibodies (parameter: selection-size).

Step 8: Update antibodies by comparing the affinity of antibodies that are selected in
step 3 and step 7.

Step 9: In each "replacement-frequency" generation, select k antibodies according to
affinity (select antibodies that have worse affinity) and kill those antibodies.
Then create k random antibodies and insert them in antibody population
(parameter: replacement-frequency and replacement-rate).

Step 10: If the iteration number reaches maximum generation number, stop. Else, go to
step 3. (parameter: number-of-generation)

HOW TO USE IT

Press the SETUP button to create a random initial antibody population.

Press the GO button to run improved clonal selection algorithm to solve the traveling salesman problem. "Eil51" problem from the literature is programmed as an example.

For running the model number-of-city slider is adjusted correctly. This parameter is used as a variable in the procedure of the model.

In each "replacement-frequency" generation the best solution tour can be seen in the VIEW.

Parameters:

Initial-population-size: This slider controls the initial population size. For example, if initial-population-size is 400, algorithm will create 400 random antibody at zeroth generation.

Number-of-generation: This slider controls maximum number of generation that limits the running time of the algorithm.

Selection-size: This slider controls selection size that is used in step 3 and step 5 of algorithm.

Clone-size: This slider controls clone size that is used in step 4 of the algorithm. Clone size parameter is not enough to determine real clone size in the algorithm. Real clone size is determined by using a function that contains clone-size parameter. Through this function, antibody which has better affinity clones more and antibody which has worse affinity clones less.

Replacement-frequency: This slider is used to determine replacement generation. For example, if replacement-frequency parameter is 20, algorithm will achieve replacement process in 20th, 40th, 60th, ... generation.

Replacement-rate: This slider controls replacement size as percentage. This parameter is used in step 9 of the proposed algorithm. For example, if antibody population size is 100 and replacement-rate is 20(%), the algorithm will kill 20 antibody that have worst affinity and then insert 20 random antibody into the population.

The "Tour Length Plot" is used to show the best, average, and worst tour length values of the solutions at each generation.

THINGS TO TRY

You can make many different experiments by changing the parameters.

CREDITS AND REFERENCES

[1] Dai, H.; Yang, Y.; Li, C., “Distance Maintaining Compact Quantum Crossover Based Clonal Selection Algorithm”, Journal of Convergence Information Technology, Volume 5, No 10, 2010.
[2] Gao, S.; Dai, H.; Yang, G.; Tang, Z., “A Novel Clonal Selection Algorithm and Its Application to Traveling Salesman Problem”, IEICE Trans. Fundamentals, Volume E90–A, No 10, 2007.
[3] De Castro, L.; Von Zuben, F., “Learning and Optimization Using The Clonal Selection Principle”, Evolutionary Computation , 239-251, 2002.
[4] Dasgupta, D.; Nino, F., Immunological Computation: Theory and Applications, Auerbach Publications, 2008.
[5] Dasgupta, D.; Yu, S.; Nino, F., “Recent Advances In Artificial Immune Systems: Models And Applications”, Applied Soft Computing , 1574-1587, 2011.
[6] Wilensky, U. (1999). NetLogo. http://ccl.northwestern.edu/netlogo/. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL.

HOW TO CITE

If you mention this model in an academic publication, we ask that you include these citations:

For the model itself:
-1) Adil Baykasoglu, Alper Saltabas, A. Serdar Tasan, Kemal Subulan (2012). Realizing artificial immune system in a multi agent simulation environment and an application to travelling salesmen problem, Submitted to “Journal of The Faculty of Engineering and Architecture of Gazi University” (In Turkish).

-2) Baykasoglu, A.; Saltabas, A.; Tasan, A.S.; Subulan, K. (2012). Improved Clonal Selection Algorithm for Travelling Salesmen Problem in NetLogo. Dokuz Eylul University, Faculty of Engineering, Department of Industrial Engineering, Tinaztepe Campus, 35160 Izmir, Turkey.

For the NetLogo software:
- Wilensky, U. (1999). NetLogo. http://ccl.northwestern.edu/netlogo/. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL.

In other publications, please use:
- Adil Baykasoglu, Alper Saltabas, A. Serdar Tasan, Kemal Subulan (2012). Realizing artificial immune system in a multi agent simulation environment and an application to travelling salesmen problem, Submitted to “Journal of The Faculty of Engineering and Architecture of Gazi University” (In Turkish).

COPYRIGHT NOTICE

Copyright: Baykasoglu, A.; Saltabas, A.; Tasan, A.S.; Subulan, K. (2012).
All rights reserved.